/*
方法一没有利用「数组 nums 已经按照升序排序」这个条件。显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；
如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
这样一来，如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。
具体地，我们设 neg 为数组nums 中负数与非负数的分界线，也就是说，nums[0] 到 nums[neg] 均为负数，而 nums[neg+1] 到 nums[n−1] 均为非负数。
当我们将数组 nums 中的数平方后，那么 nums[0] 到 nums[neg] 单调递减，nums[neg+1] 到 nums[n−1] 单调递增。
由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。
具体地，使用两个指针分别指向位置neg 和neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。
当某一指针移至边界时，另一指针还未遍历到的数依次放入答案。
 */
class Solution {
    //有序数组，负数在前，正数在后
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int negative = -1; //起始位置
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i; //找到负数最后一个位置
            } else {
                break;
            }
        }

        int[] ans = new int[n]; //定义输出的数组
        // i 负数的最后一个位置 j正数的第一个位置
        int index = 0, i = negative, j = negative + 1;
        //从中间开始往两侧遍历
        while (i >= 0 || j < n) {
            if (i < 0) { //到达边界，只计算正数的一边
                ans[index] = nums[j] * nums[j];
                ++j;
            } else if (j == n) {//正数到达边界，只计算负数的一边
                ans[index] = nums[i] * nums[i];
                --i;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {//如果负数平方小于整数，那么把负数平方放入数组
                ans[index] = nums[i] * nums[i];
                --i;
            } else {//如果负数平方大于整数，那么把正数平方放入数组
                ans[index] = nums[j] * nums[j];
                ++j;
            }
            //移动指针，等待放入下一个数
            ++index;
        }

        return ans;
    }
}
